In coded data communications, encoded symbols are transmitted over a communications channel, (e.g., a radio frequency communications channel), which is subject to various types of distortion such as co-channel and adjacent channel interference, noise, dispersion, fading, weak signal strength, etc. Trellis coding is one technique used to encode sequences of symbols to be transmitted, and in the process, introduces memory to the transmitted signal. Because of the introduced memory, the transmitted signal at any instant of time depends on previously transmitted signals. Therefore, in order to demodulate the received signal and recover the transmitted symbols, the decoding process must be performed taking into account the whole sequence of symbols.
The preferred method of symbol sequence decoding is maximum likelihood sequence estimation (MLSE) which offers a mechanism for decoding the transmitted signal optimally in the sense of minimizing the probability of error. In the MLSE method, the received sequence of signals is compared with every possible sequence of symbols that could have been transmitted. The particular sequence out of all of the possible sequences that best matches the received sequence of signals is chosen as the decoded sequence. If the length of the transmitted symbol sequence is N symbols long and there are Q possible values that each symbol can take, then the MLSE pattern matching scheme tries to determine the best match from among Q.sup.N possible sequences. However, even for modest values of Q and N, the number of potential MLSE search sequences is too complex for implementation.
One simplified solution for performing the MLSE search is provided by the well known Viterbi algorithm. To understand the Viterbi algorithm, the search problem is represented as a method of searching a trellis. FIG. 1 illustrates a simple trellis where each transmitted symbol can take one of four values. Each trellis node corresponds to one value of the transmitted symbol and is often referred to as a state. At each time instant/stage, in the trellis there are four nodes defining a four-state trellis. The set of nodes repeats for each transmitted symbol period. Transitions between nodes are called branches, and each branch is associated with a possible symbol that could have been transmitted. This structure of nodes (states) and branches (symbols) defines the trellis.
A metric or weight is formed for each branch which indicates the likelihood of the symbol corresponding to that branch being part of the true received symbol sequence. An example of a metric is the squared, absolute difference between a received signal sample and a corresponding estimate of the sample formed using the symbol associated with that branch. This metric is referred to as the squared Euclidean distance metric. A linkage of branches through the nodes forms a path. The path with the best accumulated metric (i.e., the smallest sum of the branch metrics) is chosen, and the symbols corresponding to the branches of the chosen path are output as the decoded symbols.
To streamline the search procedure, the Viterbi algorithm retains only the branch into each node/state having the best/optimal (i.e., lowest) metric and discards the remaining branches into that node/state. This best branch selection procedure significantly reduces the number of possible paths through the trellis. Then, from those possible paths, the Viterbi algorithm selects the path through the trellis that produces the minimum overall distance. Since it is only necessary to retain as many paths as there are nodes, i.e., there is only one path per state, the paths that remain at each state/node are called "survivors". The Viterbi algorithm is a recursive technique that traces an optimal path of survivors through the trellis.
The main problem with the Viterbi algorithm is that its complexity grows exponentially with the number of states (memory) of the transmitted, trellis-coded signal. With the number of states being expressed as Q.sup.N and with Q as the number of possible values a symbol can take, N represents the memory or dependence of a symbol on other symbols. A "memory of N" implies that each symbol depends on N other symbols, e.g., previous symbols. This complexity can be reduced using what is known as the M-algorithm or T-algorithm, both of which further restrict the number of states retained for decoding. In the basic M-algorithm, for each time instant in the trellis, the number of survivors is restricted to a fixed integer number M. The M-algorithm chooses the M most likely states based on the accumulated path metrics. The survivor states having larger accumulated path metrics are discarded. Another variant of the M-algorithm is to retain the best (as defined by the accumulated path metrics) M-paths through the trellis rather than M states. Hence, the M-algorithm restricts the search through the trellis to a fixed number of states M at any time instant in the trellis. Unfortunately, if the selected value for M is too small, there is a high probability of retaining the wrong M states for decoding which results in a high error probability. On the other hand, if the selected value of M is too large, the decoding procedure becomes unduly complex.
The T-algorithm retains only those states which have an associated metric that is below a predetermined threshold (T). Like the M-algorithm, the choice of the fixed threshold T is critical in order to achieve satisfactory performance without undue complexity. In practice, the selection of a threshold T for a particular communications application that is suitable for all or most conditions encountered in that application is quite difficult.
The problem with a fixed M or a fixed T is that the communications channel, over which encoded symbols are transmitted, received, and then decoded, changes. In radio frequency communications, the radio channels exhibit constantly changing parameters because of fading, multipath dispersion, adjacent channel interference, co-channel interference, noise, etc. In order to compensate for worst case scenarios for a communications channel, the value of M for the M-algorithm or the value of T for the T-algorithm must be set to a relatively large number in order to have a sufficient number of states available to satisfactorily decode the symbols under such worst case channel conditions. However, this is an inefficient decoding approach because for a large percentage of the time, the channel condition may be quite good, and a much smaller number of states is all that is needed to satisfactorily decode the received signal.
What is needed therefore is a trellis decoding procedure with reduced complexity that can adapt the number of survivor paths or states in the trellis based upon one or more conditions of the communications system. In radio communication applications, and especially battery operated, portable radios, transmit power is at a premium. However, lower transmit power may result in poor decoding performance at the receiver. There is also a need to reduce the transmit power of fixed transceivers like base station/repeaters to minimize adjacent channel interference. But this reduction is only feasible if receivers can accurately and efficiently decode the signals transmitted at lower power.